package heap;

import java.util.*;

/**
 * 面试题 17.14. 最小K个数
 * https://leetcode-cn.com/problems/smallest-k-lcci/
 */
public class 面试题17_14最小K个数 {
    public int[] smallestK(int[] arr, int k) {
        if (arr.length == 0 || k == 0){
            return new int[0];
        }
        Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            //实现Comparator可进行比较，最小堆o1 - o2,
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;//注意书写o不是0
            }
        });//优先级队列默认最小堆实现
        for (int i:arr
             ) {
            if (queue.size() < k){
                queue.offer(i);
            }else {
                if (i > queue.peek()){
                    continue;
                }else {
                    queue.poll();
                    queue.offer(i);
                }
            }

        }
        int[] ret = new int[queue.size()];
        for (int i = 0; i < ret.length; i++) {
            ret[i] = queue.poll();
        }
        return ret;
    }
}
